package com.xy6.algo.force;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 字符串全排列（有重复字符）
 * <pre>
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
 * 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 * 
 * 时间复杂度：O(n!)
 * </pre>
 * 
 * @author zhang
 * @since 2017-12-30
 */
public class ArrangeChar {

	public static void main(String[] args){
		String str = "abc";
		List<String> sort = permutation(str);
		
		for(String elem : sort){
			System.out.println(elem);
		}
	}
	
	/**
	 * 全排列一个字符串，字符可以重复
	 * 
	 * @param str
	 * @return
	 */
	public static ArrayList<String> permutation(String str){
		if(null == str){
			return null;
		}
		ArrayList<String> list = new ArrayList<>();
		char[] chars = str.toCharArray();
		list = allSort(chars, 0, list);
		Collections.sort(list);
		return list;
	}
	
	/**
	 * 对一个字符串的后n个字符进行全排列
	 * 
	 * @param chars
	 * @param index
	 * @param list
	 * @return
	 */
	private static ArrayList<String> allSort(char[] chars, int index, ArrayList<String> list){
		System.out.println(String.format("%s %d", Arrays.toString(chars), index));
		if(index == chars.length - 1){
			System.out.println(String.format("add %s", String.valueOf(chars)));
			list.add(String.valueOf(chars));
			return list;
		}
		for(int i=index; i<chars.length; i++){
			System.out.println(String.format("%s %d %d", Arrays.toString(chars), index, i));
			if(i != index && chars[i] == chars[index]){
				continue;
			}
			// 修改第一个与后面的位置
			exchangeChars(index, i, chars);
			allSort(chars, index+1, list);
			// 修改成原来的数组
			exchangeChars(index, i, chars);
		}
		
		return list;
	}
	
	/**
	 * 交换两个字符
	 * 
	 * @param index1
	 * @param index2
	 * @param chars
	 */
	private static void exchangeChars(int index1, int index2, char[] chars){
		char temp = chars[index1];
		chars[index1] = chars[index2];
		chars[index2] = temp;
	}
	
}
